package nowcoder;

import java.util.ArrayList;

/**
 * @author wangxi created on 2021/5/9 16:51
 * @version v1.0
 * https://leetcode-cn.com/problems/spiral-matrix/
 * 给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。
 */
public class SpiralOrder {

    public static void main(String[] args) {
        SpiralOrder spiralOrder = new SpiralOrder();
        int[][] matrix = {{1,2,3}, {4,5,6}, {7,8,9}};

        ArrayList<Integer> res = spiralOrder.spiralOrder(matrix);
        System.out.println(res);

    }

    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length <= 0 || matrix[0].length <= 0) {
            return res;
        }
        // 不是正方形，因此start满足的条件需要同时满足行、列
        for (int start = 0; 2 * start < matrix.length && 2 * start < matrix[0].length; start++) {
            fill(matrix, res, start);
        }
        return res;
    }

    private void fill(int[][] matrix, ArrayList<Integer> res, int start) {
        int endRow = matrix.length - start - 1;
        int endCol = matrix[0].length - start - 1;
        for (int i = start; i <= endCol; i++) {
            res.add(matrix[start][i]);
        }
        // 至少两行
        if (endRow > start) {
            for (int i = start + 1; i <= endRow; i++) {
                res.add(matrix[i][endCol]);
            }
        }
        // 至少两行两列 , 这里容易忽略掉前置条件：至少2行
        if (endCol > start && endRow > start) {
            for (int i = endCol - 1; i >= start; i--) {
                res.add(matrix[endRow][i]);
            }
        }
        // 至少三行两列
        if (endRow > start + 1 && endCol > start) {
            for (int i = endRow - 1; i > start; i--) {
                res.add(matrix[i][start]);
            }
        }
    }
}
